package com.cb2.algorithm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string">删除字符串中的所有相邻重复项(Remove All Adjacent Duplicates In String)</a>
 * <p>给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。</p>
 * <p>在 s 上反复执行重复项删除操作，直到无法继续删除。</p>
 * <p>在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例：
 *      输入："abbaca"
 *      输出："ca"
 *      解释：
 *          例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。
 *          之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ol>
 *     <li>1 <= s.length <= 10^5</li>
 *     <li>s 仅由小写英文字母组成。</li>
 * </ol>
 * </p>
 *
 * @author c2b
 * @since 2025/2/7 16:45
 */
public class LC1047RemoveAllAdjacentDuplicatesInString_S {
    static class Solution {
        public String removeDuplicates(String s) {
            char[] cnt = new char[s.length()];
            int idx = -1;
            for (char c : s.toCharArray()) {
                if (idx >= 0 && cnt[idx] == c) {
                    --idx;
                } else {
                    cnt[++idx] = c;
                }
            }
            return new String(cnt, 0, idx + 1);
        }

        public String removeDuplicates2(String s) {
            StringBuilder stack = new StringBuilder();
            int top = -1;   // 用来记录栈顶的位置，避免多次调用stack.length()函数
            for (char c : s.toCharArray()) {
                if (top >= 0 && stack.charAt(top) == c) {
                    stack.deleteCharAt(top);
                    --top;
                } else {
                    stack.append(c);
                    ++top;
                }
            }
            return stack.toString();
        }

        public String removeDuplicates3(String s) {
            Deque<Character> stack = new LinkedList<>();
            for (char c : s.toCharArray()) {
                if (!stack.isEmpty() && stack.peekFirst() == c) {
                    stack.removeFirst();
                } else {
                    stack.addFirst(c);
                }
            }
            StringBuilder res = new StringBuilder();
            while (!stack.isEmpty()) {
                res.append(stack.removeFirst());
            }
            return res.reverse().toString();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.removeDuplicates("abbaca"));
        System.out.println(solution.removeDuplicates("abba"));
    }

}
